package com.msa.data;

/**
 * @author 毕子航 951755883@qq.com
 * @date 2018/12/21
 */
public class MyOrderArray {
	int[] arr;
	int elements;

	public MyOrderArray(int size) {
		this.arr = new int[size];
		this.elements = 0;
	}

	/**
	 * 有序插入
	 *
	 * @param value
	 */
	public void add(int value) {
		check();
		int position = -1;
		//寻找第一个大于value的元素的下标
		for (int i = 0; i < elements; i++) {
			if (arr[i] >= value) {
				position = i;
				break;
			}
		}
		if (position > -1) {
			//移动后面的元素
			for (int j = elements; j > position; j--) {
				arr[j] = arr[j - 1];
			}
			arr[position] = value;
		} else {
			arr[elements] = value;
		}
		elements++;
	}

	/**
	 * 获取指定位置的元素
	 *
	 * @param index
	 * @return
	 */
	public int get(int index) {
		check(index);
		return arr[index];
	}

	/**
	 * 查找数组中元素等于value的下表
	 *
	 * @param value
	 * @return
	 */
	public int indexOf(int value) {
		int minIndex = 0;
		int maxIndex = elements;
		int middleIndex = 0;
		while (true) {
			middleIndex = (maxIndex + minIndex) / 2;
			if (arr[elements - 1] < value || arr[minIndex] > value) {
				return -1;
			}

			if (arr[middleIndex] == value) {
				return middleIndex;
			} else {
				if (arr[middleIndex] > value) {
					maxIndex = middleIndex - 1;
				} else {
					minIndex = middleIndex + 1;
				}
			}
		}

	}

	/**
	 * 更改
	 *
	 * @param index
	 * @param value
	 */
	public void set(int index, int value) {
		check(index);
		remove(index);
		add(value);
	}

	/**
	 * 删除指定index的元素
	 *
	 * @param index
	 */
	public void remove(int index) {
		check(index);
		int maxIndex = elements - 1;
		if (index != maxIndex) {
			for (int i = index; i < maxIndex; i++) {
				arr[i] = arr[i + 1];
			}
		}
		elements--;
	}

	/**
	 * 获取总数
	 *
	 * @return
	 */
	public int size() {
		return elements;
	}

	private void throwException() {
		throw new ArrayIndexOutOfBoundsException("容器大小不足");
	}

	/**
	 * 检查数组是否越界
	 *
	 * @throws ArrayIndexOutOfBoundsException
	 */
	private void check() throws ArrayIndexOutOfBoundsException {
		if (elements > arr.length) {
			throwException();
		}
	}


	/**
	 * 检查下标是否越界
	 *
	 * @param index
	 * @throws ArrayIndexOutOfBoundsException
	 */
	private void check(int index) throws ArrayIndexOutOfBoundsException {
		check();
		if (index >= elements) {
			throwException();
		}
	}

	/**
	 * 打印数据
	 */
	public void display() {
		System.out.print("[");
		for (int i = 0; i < elements; i++) {
			System.out.print(i + "=" + arr[i] + " ");
		}
		System.out.print("]");
		System.out.println();
	}
}
